package datastructure;

/**
 * operation O(logn), segment tree for calculating sum
 * 
 * @author yinzichen
 * 
 */
public class SegmentTree {
	int[] seg;
	int size;

	public void init(int n) {
		size = n;
		seg = new int[n << 2];
		build(1, n, 1);
	}

	private void build(int l, int r, int root) {
		seg[root] = 0;
		if (l == r)
			return;
		build(l, l + r >> 1, root << 1);
		build((l + r >> 1) + 1, r, (root << 1) + 1);
	}

	public void add(int n, int v) {
		add(1, size, 1, n, v);
	}

	private void add(int l, int r, int root, int n, int v) {
		seg[root] += v;
		if (l == r)
			return;
		int mid = l + r >> 1;
		if (n <= mid) {
			add(l, mid, root << 1, n, v);
		} else {
			add(mid + 1, r, (root << 1) + 1, n, v);
		}
	}

	public int sum(int n) {
		return sum(1, size, 1, n);
	}

	private int sum(int l, int r, int root, int n) {
		if (n >= r)
			return seg[root];
		int mid = l + r >> 1;
		if (n <= mid) {
			return sum(l, mid, root << 1, n);
		} else {
			return sum(l, mid, root << 1, n)
					+ sum(mid + 1, r, (root << 1) + 1, n);
		}
	}
}
